package leetcode_day._2023._12;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 1631.最小体力消耗路径
 * 算法: 并查集
 *
 * @author yezh
 * @date 2023/12/11 15:29
 */
public class _11 {

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        List<int[]> edges = new ArrayList<>(2 * m * n - m - n);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int pos = i * n + j;
                if (j + 1 < n)
                    edges.add(new int[]{Math.abs(heights[i][j] - heights[i][j + 1]), pos, pos + 1});
                if (i + 1 < m)
                    edges.add(new int[]{Math.abs(heights[i][j] - heights[i + 1][j]), pos, pos + n});
            }
        edges.sort(Comparator.comparingInt(a -> a[0]));
        int[] p = new int[m * n];
        for (int i = 0; i < m * n; i++) p[i] = i;
        for (int[] edge : edges) {
            union(edge[1], edge[2], p);
            if (find(0, p) == find(m * n - 1, p)) return edge[0];
        }
        return 0;
    }

    void union(int c1, int c2, int[] parent) {
        parent[find(c1, parent)] = find(c2, parent);
    }

    int find(int c, int[] parent) {
        int p = parent[c];
        if (c != p) parent[c] = find(p, parent);
        return parent[c];
    }

}
